{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #路径总和 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #路径总和 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的根节点 <code>root</code>&nbsp;，和一个整数 <code>targetSum</code> ，求该二叉树里节点值之和等于 <code>targetSum</code> 的 <strong>路径</strong> 的数目。</p>\n",
    "\n",
    "<p><strong>路径</strong> 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/09/pathsum3-1-tree.jpg\" style=\"width: 452px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>和等于 8 的路径有 3 条，如图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[0,1000]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-10<sup><span style=\"font-size: 9.449999809265137px;\">9</span></sup>&nbsp;&lt;= Node.val &lt;= 10<sup><span style=\"font-size: 9.449999809265137px;\">9</span></sup></code>&nbsp;</li>\n",
    "\t<li><code>-1000&nbsp;&lt;= targetSum&nbsp;&lt;= 1000</code>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 437&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/path-sum-iii/\">https://leetcode-cn.com/problems/path-sum-iii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [6eUYwP](https://leetcode.cn/problems/6eUYwP/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [6eUYwP](https://leetcode.cn/problems/6eUYwP/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,5,-3,3,2,null,11,3,-2,null,1]\\n8', '[5,4,8,11,null,13,4,7,2,null,null,5,1]\\n22']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        if root is None:\n",
    "            return res\n",
    "\n",
    "        def dfs(root, pathSum):\n",
    "            nonlocal res\n",
    "            # 只遍历非空节点\n",
    "            if root.left is None and root.right is None:\n",
    "                res += pathSum * 10 + root.val\n",
    "                return\n",
    "\n",
    "            pathSum = pathSum * 10 + root.val\n",
    "            if root.left is not None:\n",
    "                dfs(root.left, pathSum)\n",
    "            if root.right is not None:\n",
    "                dfs(root.right, pathSum)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if root is None:\n",
    "            return 0            \n",
    "        stack = [(root,root.val,True)]\n",
    "        ans = 0\n",
    "        while stack:\n",
    "            thisRoot,num,flag = stack.pop()\n",
    "            if num == targetSum:\n",
    "                ans += 1\n",
    "            if thisRoot.left:\n",
    "                stack.append((thisRoot.left,num + thisRoot.left.val,flag))\n",
    "                if flag:\n",
    "                    stack.append((thisRoot.left,thisRoot.left.val,False))\n",
    "            if thisRoot.right:\n",
    "                stack.append((thisRoot.right,num + thisRoot.right.val,flag))\n",
    "                if flag:\n",
    "                    stack.append((thisRoot.right,thisRoot.right.val,False))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "\n",
    "        if root is None: return 0\n",
    "\n",
    "        def inner(node, ssum):\n",
    "            if node is None: return 0\n",
    "            res = 0\n",
    "            if node.val == ssum:\n",
    "                res += 1\n",
    "            res += inner(node.left, ssum - node.val)\n",
    "            res += inner(node.right, ssum - node.val)\n",
    "            return res\n",
    "        \n",
    "        res = inner(root, targetSum)\n",
    "        res += self.pathSum(root.left, targetSum)\n",
    "        res += self.pathSum(root.right, targetSum)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        \"\"\"\n",
    "        解题思路：递归+穷举，我们遍历每一个节点，计算这个节点向下延申的长度等于targetSum的路径有多少条\n",
    "        \"\"\"\n",
    "        # 函数是为了递归计算路径\n",
    "        def get_sum(root: TreeNode, targetSum: int) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            cur_res = 0\n",
    "            if targetSum == root.val:\n",
    "                cur_res += 1\n",
    "            cur_res += get_sum(root.left, targetSum-root.val)\n",
    "            cur_res += get_sum(root.right, targetSum-root.val)\n",
    "            return cur_res\n",
    "\n",
    "        # special case\n",
    "        if not root:\n",
    "            return 0\n",
    "        # 递归函数入口，用前序遍历访问每一个节点，注意这里的第2个参数，这个位置是遍历，不是递归\n",
    "        res = get_sum(root, targetSum)\n",
    "        res += self.pathSum(root.left, targetSum)\n",
    "        res += self.pathSum(root.right, targetSum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        self.ans = 0\n",
    "        pre_sum_map = defaultdict(int)\n",
    "        pre_sum_map[0] = 1\n",
    "\n",
    "        def helper(node: TreeNode, prev: int):\n",
    "            if not node:\n",
    "                return\n",
    "            prev += node.val\n",
    "            self.ans += pre_sum_map.get(prev - targetSum, 0)\n",
    "            pre_sum_map[prev] += 1\n",
    "            helper(node.left, prev)\n",
    "            helper(node.right, prev)\n",
    "            pre_sum_map[prev] -= 1\n",
    "            prev -= node.val\n",
    "        helper(root, 0)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        pre_num = defaultdict(int)\n",
    "        pre_num[0] = 1\n",
    "        self.ans = 0\n",
    "\n",
    "        def helper(node: TreeNode, prev):\n",
    "            if not node:\n",
    "                return\n",
    "            prev += node.val\n",
    "            if prev - targetSum in pre_num:\n",
    "                self.ans += pre_num[prev - targetSum]\n",
    "            pre_num[prev] += 1\n",
    "            helper(node.left, prev)\n",
    "            helper(node.right, prev)\n",
    "            pre_num[prev] -= 1\n",
    "            prev -= node.val\n",
    "        helper(root, 0)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def rootSum(root, targetSum) -> int:\n",
    "            if root == None:\n",
    "                return 0\n",
    "            ret = 0\n",
    "            if root.val == targetSum:\n",
    "                ret += 1\n",
    "            ret += rootSum(root.left, targetSum - root.val)\n",
    "            ret += rootSum(root.right, targetSum - root.val)\n",
    "            return ret\n",
    "        if root == None:\n",
    "            return 0\n",
    "        ret = rootSum(root, targetSum)\n",
    "        ret += self.pathSum(root.left, targetSum)\n",
    "        ret += self.pathSum(root.right, targetSum)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "\n",
    "        # top-down or bottom-up should both OK\n",
    "        # prefix sum idea + dfs\n",
    "\n",
    "        # ret = 0\n",
    "        # def dfs(n, d):\n",
    "        #     if not n:\n",
    "        #         return\n",
    "\n",
    "        #     # print({k:v for k, v in d.items() if v != 0})\n",
    "\n",
    "        #     t = targetSum - n.val\n",
    "        #     nonlocal ret\n",
    "        #     # if d[t] != 0:\n",
    "        #     #     print(f'{n.val} {t} {d[t]}')   \n",
    "        #     ret += d[t]\n",
    "\n",
    "        #     # above check is the path start is from root to current parent and end is current\n",
    "        #     # so if t==0 then only current is satisfy the condition\n",
    "        #     # so stand alone check t == 0 make sense\n",
    "        #     if t == 0:\n",
    "        #         ret += 1\n",
    "\n",
    "        #     nd = defaultdict(int)\n",
    "        #     nd[n.val] = 1\n",
    "        #     for k, v in d.items():\n",
    "        #         nd[k+n.val] += v\n",
    "            \n",
    "        #     # for k, v in nd.items():\n",
    "        #     #     d[k] += v\n",
    "\n",
    "        #     dfs(n.left, nd)\n",
    "        #     dfs(n.right, nd)\n",
    "\n",
    "            \n",
    "        #     # for k, v in nd.items():\n",
    "        #     #     d[k] -= v\n",
    "        \n",
    "        # d = defaultdict(int)\n",
    "        # # d[0] = 1\n",
    "        # dfs(root, d)\n",
    "\n",
    "        # return ret\n",
    "\n",
    "        # from ans, above solution doesn't use prefix at all\n",
    "        # d should record the all path sum from root to any ancestor of the cur node (prefix)\n",
    "        # and from root to cur node sum - targetVal if in d, then it means the ancester to cur node equal targetVal\n",
    "        # wholeSum - targetVal = prefixSum\n",
    "        # targetVal = wholeSum - prefixSum\n",
    "        # targetVal = sum(ancester to cur node)\n",
    "\n",
    "        ret = 0\n",
    "        def dfs(n, d, s):\n",
    "            if not n:\n",
    "                return\n",
    "\n",
    "            print({k:v for k, v in d.items() if v != 0})\n",
    "            s += n.val\n",
    "            t = s - targetSum\n",
    "            nonlocal ret\n",
    "            if d[t] != 0:\n",
    "                print(f'{s} {n.val} {t} {d[t]}')   \n",
    "            ret += d[t]\n",
    "\n",
    "            d[s] += 1\n",
    "            \n",
    "            dfs(n.left, d, s)\n",
    "            dfs(n.right, d, s)\n",
    "\n",
    "            d[s] -= 1\n",
    "        \n",
    "        d = defaultdict(int)\n",
    "\n",
    "        # key is put prefix sum(0)\n",
    "        # thus include the situation from root to leaf\n",
    "        # this solution slower than previous unexpected\n",
    "        d[0] = 1\n",
    "        dfs(root, d, 0)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "\n",
    "        # top-down or bottom-up should both OK\n",
    "        # prefix sum idea + dfs\n",
    "\n",
    "        # ret = 0\n",
    "        # def dfs(n, d):\n",
    "        #     if not n:\n",
    "        #         return\n",
    "\n",
    "        #     # print({k:v for k, v in d.items() if v != 0})\n",
    "\n",
    "        #     t = targetSum - n.val\n",
    "        #     nonlocal ret\n",
    "        #     # if d[t] != 0:\n",
    "        #     #     print(f'{n.val} {t} {d[t]}')   \n",
    "        #     ret += d[t]\n",
    "\n",
    "        #     # above check is the path start is from root to current parent and end is current\n",
    "        #     # so if t==0 then only current is satisfy the condition\n",
    "        #     # so stand alone check t == 0 make sense\n",
    "        #     if t == 0:\n",
    "        #         ret += 1\n",
    "\n",
    "        #     nd = defaultdict(int)\n",
    "        #     nd[n.val] = 1\n",
    "        #     for k, v in d.items():\n",
    "        #         nd[k+n.val] += v\n",
    "            \n",
    "        #     # for k, v in nd.items():\n",
    "        #     #     d[k] += v\n",
    "\n",
    "        #     dfs(n.left, nd)\n",
    "        #     dfs(n.right, nd)\n",
    "\n",
    "            \n",
    "        #     # for k, v in nd.items():\n",
    "        #     #     d[k] -= v\n",
    "        \n",
    "        # d = defaultdict(int)\n",
    "        # # d[0] = 1\n",
    "        # dfs(root, d)\n",
    "\n",
    "        # return ret\n",
    "\n",
    "        # from ans, above solution doesn't use prefix at all\n",
    "        # d should record the all path sum from root to any ancestor of the cur node (prefix)\n",
    "        # and from root to cur node sum - targetVal if in d, then it means the ancester to cur node equal targetVal\n",
    "        # wholeSum - targetVal = prefixSum\n",
    "        # targetVal = wholeSum - prefixSum\n",
    "        # targetVal = sum(ancester to cur node)\n",
    "\n",
    "        ret = 0\n",
    "        def dfs(n, d, s):\n",
    "            if not n:\n",
    "                return\n",
    "\n",
    "            print({k:v for k, v in d.items() if v != 0})\n",
    "            s += n.val\n",
    "            t = s - targetSum\n",
    "            nonlocal ret\n",
    "            if d[t] != 0:\n",
    "                print(f'{s} {n.val} {t} {d[t]}')   \n",
    "            ret += d[t]\n",
    "\n",
    "            d[s] += 1\n",
    "            \n",
    "            dfs(n.left, d, s)\n",
    "            dfs(n.right, d, s)\n",
    "\n",
    "            d[s] -= 1\n",
    "        \n",
    "        d = defaultdict(int)\n",
    "\n",
    "        # key is put prefix sum(0)\n",
    "        # thus include the situation from root to leaf\n",
    "        # this solution slower than previous unexpected\n",
    "        d[0] = 1\n",
    "        dfs(root, d, 0)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        root.pre = ()\n",
    "        s = [root]\n",
    "        ans = 0\n",
    "        while s:\n",
    "            node = s.pop()\n",
    "            if node.left:\n",
    "                node.left.pre = node.pre + (node.val,)\n",
    "                s.append(node.left)\n",
    "            if node.right:\n",
    "                node.right.pre = node.pre + (node.val,)\n",
    "                s.append(node.right)\n",
    "            Sum = node.val\n",
    "            if Sum == targetSum:\n",
    "                ans += 1\n",
    "            for x in node.pre[::-1]:\n",
    "                Sum += x\n",
    "                if Sum == targetSum:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# 方法一：深度优先搜索，更好理解\n",
    "class Solution:\n",
    "    @cache\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def rootSum(node, target):\n",
    "            if not node: return 0\n",
    "            ret = 0\n",
    "            if node.val == target:\n",
    "                ret += 1\n",
    "            ret += rootSum(node.left, target - node.val)\n",
    "            ret += rootSum(node.right, target - node.val)\n",
    "            return ret\n",
    "        \n",
    "        if not root: return 0\n",
    "        ret = rootSum(root, targetSum)\n",
    "        ret += self.pathSum(root.left, targetSum)\n",
    "        ret += self.pathSum(root.right, targetSum)\n",
    "        return ret\n",
    "\n",
    "\n",
    "# # 方法二: 前缀和\n",
    "# class Solution:\n",
    "#     def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "#         def dfs(node, curr):\n",
    "#             if not node: return 0\n",
    "#             ret = 0\n",
    "#             curr += node.val\n",
    "#             ret += prefix[curr - targetSum]\n",
    "#             prefix[curr] += 1\n",
    "#             ret += dfs(node.left, curr)\n",
    "#             ret += dfs(node.right, curr)\n",
    "#             prefix[curr] -= 1\n",
    "#             return ret\n",
    "\n",
    "#         prefix = collections.Counter()\n",
    "#         prefix[0] = 1\n",
    "#         return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "\n",
    "        res=0\n",
    "        def recur(node,ll):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return \n",
    "            cur=node.val\n",
    "            if cur==targetSum:\n",
    "                res+=1\n",
    "            for x in ll[::-1]:\n",
    "                cur+=x\n",
    "                if cur==targetSum:\n",
    "                    res+=1\n",
    "            recur(node.left,ll+[node.val])\n",
    "            recur(node.right,ll+[node.val])\n",
    "        recur(root,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node ,pre):\n",
    "            if not node:\n",
    "                return\n",
    "            cur = pre[-1] + node.val\n",
    "            for p in pre:\n",
    "                if cur - p == targetSum:\n",
    "                    self.ans += 1\n",
    "            new_pre = pre + [cur]\n",
    "            dfs(node.left, new_pre)\n",
    "            dfs(node.right, new_pre)\n",
    "        \n",
    "\n",
    "        dfs(root, [0])\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        ret= 0\n",
    "        path = [0]\n",
    "        def dfs(root,prev,path):\n",
    "            if not root:\n",
    "                return 0\n",
    "            total = prev + root.val\n",
    "            nonlocal ret\n",
    "            ret += path.count(total-targetSum)\n",
    "            path.append(total)\n",
    "            p = path.copy()\n",
    "            dfs(root.left,total,p)\n",
    "            dfs(root.right,total,path)\n",
    "        \n",
    "        dfs(root,0,path)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node,nums):\n",
    "            if not node: return\n",
    "            nums.append(node.val)\n",
    "            for i in range(len(nums)):\n",
    "                if sum(nums[i:])==targetSum:self.res+=1\n",
    "            dfs(node.left,nums[:])\n",
    "            dfs(node.right,nums[:])\n",
    "        dfs(root,[])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return self.path_sum(root, targetSum, [])\n",
    "\n",
    "    def path_sum(\n",
    "        self,\n",
    "        root: Optional[TreeNode],\n",
    "        targetSum: int,\n",
    "        r_sum: List[int],\n",
    "    ) -> int:\n",
    "        sum_path = root.val + (r_sum[-1] if len(r_sum) > 0 else 0)\n",
    "        num_paths = 1 if sum_path == targetSum else 0\n",
    "        for r in r_sum:\n",
    "            if sum_path - r == targetSum:\n",
    "                num_paths += 1\n",
    "        if root.left is not None:\n",
    "            num_paths += self.path_sum(\n",
    "                root.left,\n",
    "                targetSum,\n",
    "                r_sum + [sum_path],\n",
    "            )\n",
    "        if root.right is not None:\n",
    "            num_paths += self.path_sum(\n",
    "                root.right,\n",
    "                targetSum,\n",
    "                r_sum + [sum_path],\n",
    "            )\n",
    "        return num_paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def traverse(node, pre, lst, ans):\n",
    "            if node is None:\n",
    "                return ans\n",
    "            node.pre = pre + node.val\n",
    "            print(node.pre, lst)\n",
    "            if node.pre == targetSum:\n",
    "                ans += 1\n",
    "            for i in range(len(lst)):\n",
    "                if node.pre - lst[i] == targetSum:\n",
    "                    ans = ans + 1\n",
    "            lst.append(node.pre)\n",
    "            ans = traverse(node.left, node.pre, lst.copy(), ans)\n",
    "            ans = traverse(node.right, node.pre, lst.copy(), ans)\n",
    "            return ans\n",
    "        ans = traverse(root, 0, [], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        def dfs(node, prefix):\n",
    "            nonlocal count\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            last = 0 if not prefix else prefix[-1]\n",
    "\n",
    "            now = last + node.val\n",
    "\n",
    "            \n",
    "            if now == targetSum:\n",
    "                count += 1\n",
    "\n",
    "            if now - targetSum in prefix:\n",
    "                count += prefix.count(now - targetSum)\n",
    "            \n",
    "            prefix.append(now)\n",
    "\n",
    "\n",
    "            dfs(node.left, prefix.copy())\n",
    "            dfs(node.right, prefix.copy())\n",
    "        \n",
    "        dfs(root, [])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def v2(node,targetSum):\n",
    "            res,leaf,que,cnt=[[[node.val]]],[],[[node,1,[]]],0\n",
    "            while que:\n",
    "                node,h,path =que.pop(0)\n",
    "                if not node:continue\n",
    "                while h>=len(res):res.append([])\n",
    "                que.append([node.left,h+1,path+[node.val]])\n",
    "                que.append([node.right,h+1,path+[node.val]])  \n",
    "                pa = path+[node.val]\n",
    "                res[h].append(pa)\n",
    "                cum=0\n",
    "                for j in range(len(pa)-1,-1,-1):\n",
    "                    cum += pa[j]\n",
    "                    if cum==targetSum:cnt+=1\n",
    "            return cnt\n",
    "        return v2(root,targetSum) if root else 0        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res=[]\n",
    "        # 在以node为根节点的路径当中是否存在和为targetSum的路径\n",
    "        def batktracking(node,targetSum):\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val==targetSum:\n",
    "                res.append(1)\n",
    "            batktracking(node.left,targetSum-node.val)\n",
    "            batktracking(node.right,targetSum-node.val)\n",
    "        \n",
    "        stack=[root]\n",
    "        while(stack):\n",
    "            node=stack.pop()\n",
    "            batktracking(node,targetSum)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        # 前缀和\n",
    "        ans = []\n",
    "        def dfs(node, value, nums):\n",
    "            value += node.val\n",
    "            if value == targetSum:\n",
    "                ans.append(1)\n",
    "            for num in nums:\n",
    "                if num == value - targetSum:\n",
    "                    ans.append(1)\n",
    "            nums.append(value)\n",
    "            if node.left:\n",
    "                dfs(node.left, value, nums)\n",
    "                nums.pop()\n",
    "            if node.right:\n",
    "                dfs(node.right, value, nums)\n",
    "                nums.pop()\n",
    "        if root is None:\n",
    "            return 0\n",
    "        dfs(root, 0, []) \n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        self.getPath(root, targetSum)\n",
    "        return self.res\n",
    "\n",
    "    def getPath(self, node, targetSum):\n",
    "        if not node:\n",
    "            return []\n",
    "        tmp = [[node.val]]\n",
    "        if node.val == targetSum:\n",
    "            self.res += 1\n",
    "\n",
    "        if node.left:\n",
    "            for p in self.getPath(node.left, targetSum):\n",
    "                new_path = [node.val] + p\n",
    "                if sum(new_path) == targetSum:\n",
    "                    self.res += 1\n",
    "                tmp.append(new_path)\n",
    "                \n",
    "        if node.right:\n",
    "            for p in self.getPath(node.right, targetSum):\n",
    "                new_path = [node.val] + p\n",
    "                if sum(new_path) == targetSum:\n",
    "                    self.res += 1\n",
    "                tmp.append(new_path)\n",
    "        \n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        self.getPath(root, targetSum)\n",
    "        return self.res\n",
    "\n",
    "    def getPath(self, node, targetSum):\n",
    "        if not node:\n",
    "            return []\n",
    "        tmp = [[node.val]]\n",
    "        if node.val == targetSum:\n",
    "            self.res += 1\n",
    "\n",
    "        if node.left:\n",
    "            for p in self.getPath(node.left, targetSum):\n",
    "                new_path = [node.val] + p\n",
    "                if sum(new_path) == targetSum:\n",
    "                    self.res += 1\n",
    "                tmp.append(new_path)\n",
    "                \n",
    "        if node.right:\n",
    "            for p in self.getPath(node.right, targetSum):\n",
    "                new_path = [node.val] + p\n",
    "                if sum(new_path) == targetSum:\n",
    "                    self.res += 1\n",
    "                tmp.append(new_path)\n",
    "        \n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        sum_dict = defaultdict(int)\n",
    "        father_dict = defaultdict(list)\n",
    "\n",
    "        def dfs(node,sum_cur,node_pre):\n",
    "            sum_cur += node.val\n",
    "            sum_dict[node]=sum_cur\n",
    "            if node_pre != None:\n",
    "                father_dict[node] = father_dict[node_pre]+[node_pre]\n",
    "            if node.left:\n",
    "                dfs(node.left,sum_cur,node)\n",
    "            if node.right:\n",
    "                dfs(node.right,sum_cur,node)\n",
    "        \n",
    "        dfs(root,0,None)\n",
    "        res = [0]\n",
    "        def dfs_view(node):\n",
    "            if sum_dict[node] == targetSum:\n",
    "                    res[0]+=1\n",
    "            for i in father_dict[node]:\n",
    "                if sum_dict[node] - sum_dict[i] == targetSum:\n",
    "                    res[0]+=1\n",
    "\n",
    "            if node.left:\n",
    "                dfs_view(node.left)\n",
    "            if node.right:\n",
    "                dfs_view(node.right)\n",
    "        dfs_view(root)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int, pre=0, presum=None) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        if presum is None:\n",
    "            presum = Counter()\n",
    "            presum[pre] += 1\n",
    "        \n",
    "        pre += root.val\n",
    "        ans = presum[pre - targetSum]\n",
    "        presum[pre] += 1\n",
    "\n",
    "        ans += self.pathSum(root.left, targetSum, pre, presum.copy())\n",
    "        ans += self.pathSum(root.right, targetSum, pre, presum)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.count=0\n",
    "        def recur(cur,sums):\n",
    "            if not cur:return \n",
    "           \n",
    "            sums.append(sums[-1]+cur.val)\n",
    "            s1=sums[:]\n",
    "            s2=s1[:]\n",
    "            n=len(sums)\n",
    "            for  i in range(n-1):\n",
    "                if sums[-1]-sums[i]==targetSum:\n",
    "                   \n",
    "                    self.count+=1\n",
    "            recur(cur.left,s1)\n",
    "            recur(cur.right,s2)\n",
    "        \n",
    "        recur(root,[0])\n",
    "        return self.count\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def fun(node):\n",
    "            hashmap[node.val] += 1\n",
    "            ref = collections.defaultdict(int)\n",
    "            ref[node.val] = 1\n",
    "            if node.left:\n",
    "                for k, v in fun(node.left).items():\n",
    "                    ref[k + node.val] += v\n",
    "                    hashmap[k + node.val] += v\n",
    "            if node.right:\n",
    "                for k, v in fun(node.right).items():\n",
    "                    ref[k + node.val] += v\n",
    "                    hashmap[k + node.val] += v\n",
    "            return ref\n",
    "        \n",
    "        if not root: return 0\n",
    "        hashmap = collections.defaultdict(int)\n",
    "        fun(root)\n",
    "        \n",
    "        return hashmap[targetSum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def fun(node):\n",
    "            if not node: return {}\n",
    "            hashmap[node.val] += 1\n",
    "            ref = collections.defaultdict(int)\n",
    "            ref[node.val] = 1\n",
    "            for k, v in fun(node.left).items():\n",
    "                ref[k + node.val] += v\n",
    "                hashmap[k + node.val] += v\n",
    "            for k, v in fun(node.right).items():\n",
    "                ref[k + node.val] += v\n",
    "                hashmap[k + node.val] += v\n",
    "            return ref\n",
    "        \n",
    "        hashmap = collections.defaultdict(int)\n",
    "        fun(root)\n",
    "        \n",
    "        return hashmap[targetSum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue = []\n",
    "        res = 0\n",
    "        def dfs(root, *head_map):\n",
    "            new_val = root.val+head_map[-1]\n",
    "            nonlocal targetSum, res\n",
    "            for val in head_map:\n",
    "                if new_val-val == targetSum:\n",
    "                    res += 1\n",
    "            head_map_chl = list(head_map)\n",
    "            head_map_chl.append(new_val)\n",
    "            if root.left:\n",
    "                dfs(root.left, *head_map_chl)\n",
    "            if root.right:\n",
    "                dfs(root.right, *head_map_chl)\n",
    "        dfs(root, *[0])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(root: TreeNode, target):\n",
    "            if not root:\n",
    "                return None\n",
    "            path.append(root.val)\n",
    "            target -= root.val\n",
    "            if target == 0:\n",
    "                self.res += 1 \n",
    "            dfs(root.left, target)\n",
    "            dfs(root.right, target)\n",
    "        dfs(root, targetSum)\n",
    "        self.pathSum(root.left, targetSum)\n",
    "        self.pathSum(root.right, targetSum)\n",
    "        return self.res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "#         def rootSum(root, targetSum):\n",
    "#             if root is None:\n",
    "#                 return 0\n",
    "\n",
    "#             ret = 0\n",
    "#             if root.val == targetSum:\n",
    "#                 ret += 1\n",
    "\n",
    "#             ret += rootSum(root.left, targetSum - root.val)\n",
    "#             ret += rootSum(root.right, targetSum - root.val)\n",
    "#             return ret\n",
    "        \n",
    "#         if root is None:\n",
    "#             return 0\n",
    "            \n",
    "#         ret = rootSum(root, targetSum)\n",
    "#         ret += self.pathSum(root.left, targetSum)\n",
    "#         ret += self.pathSum(root.right, targetSum)\n",
    "#         return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        q = deque([root])\n",
    "        res = 0 if root.val!=targetSum else 1\n",
    "        dic = {}\n",
    "        dic[root] = [root.val]\n",
    "        while q:\n",
    "            v = q.popleft()\n",
    "            vsum = dic[v]\n",
    "            if v.left:\n",
    "                q.append(v.left)\n",
    "                lsum = []\n",
    "                lval = v.left.val\n",
    "                for i in range(len(vsum)):\n",
    "                    a = vsum[i] + lval\n",
    "                    lsum.append(a)\n",
    "                    if a==targetSum:\n",
    "                        res+=1\n",
    "                lsum.append(lval)\n",
    "                if lval==targetSum:\n",
    "                    res+=1\n",
    "                dic[v.left] = lsum\n",
    "            if v.right:\n",
    "                q.append(v.right)\n",
    "                rsum = []\n",
    "                rval = v.right.val\n",
    "                for i in range(len(vsum)):\n",
    "                    b = vsum[i] + rval\n",
    "                    rsum.append(b)\n",
    "                    if b==targetSum:\n",
    "                        res+=1\n",
    "                rsum.append(rval)\n",
    "                if rval==targetSum:\n",
    "                    res+=1\n",
    "                dic[v.right] = rsum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        q = deque([root])\n",
    "        res = 0 if root.val!=targetSum else 1\n",
    "        dic = {}\n",
    "        dic[root] = [root.val]\n",
    "        while q:\n",
    "            v = q.popleft()\n",
    "            vsum = dic[v]\n",
    "            if v.left:\n",
    "                q.append(v.left)\n",
    "                lsum = []\n",
    "                lval = v.left.val\n",
    "                for i in range(len(vsum)):\n",
    "                    a = vsum[i] + lval\n",
    "                    lsum.append(a)\n",
    "                    if a==targetSum:\n",
    "                        res+=1\n",
    "                lsum.append(lval)\n",
    "                if lval==targetSum:\n",
    "                    res+=1\n",
    "                dic[v.left] = lsum\n",
    "            if v.right:\n",
    "                q.append(v.right)\n",
    "                rsum = []\n",
    "                rval = v.right.val\n",
    "                for i in range(len(vsum)):\n",
    "                    b = vsum[i] + rval\n",
    "                    rsum.append(b)\n",
    "                    if b==targetSum:\n",
    "                        res+=1\n",
    "                rsum.append(rval)\n",
    "                if rval==targetSum:\n",
    "                    res+=1\n",
    "                dic[v.right] = rsum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        self.ans = 0\n",
    "        self.dct = dict()\n",
    "        if not root:\n",
    "            return self.ans\n",
    "\n",
    "        def find_count(path):\n",
    "\n",
    "            prefix = [0, path[0].val]\n",
    "            for node in path[1:]:\n",
    "                prefix.append(prefix[-1]+node.val)\n",
    "\n",
    "            n = len(prefix)\n",
    "            temp = dict()\n",
    "            for i in range(n-1):\n",
    "                for j in range(i+1, n):\n",
    "                    if prefix[j] - prefix[i] == targetSum:\n",
    "                        if self.dct.get(path[i], {}).get(path[j-1], 0) == 0:\n",
    "                            self.ans += 1\n",
    "                            self.dct[path[i]] = self.dct.get(path[i], {})\n",
    "                            self.dct[path[i]][path[j-1]] = 1\n",
    "            return \n",
    "\n",
    "        def bfs(stack):\n",
    "            while stack:\n",
    "                lst = []\n",
    "                for path in stack:\n",
    "                    if not path[-1].left and not path[-1].right:\n",
    "                        find_count(path)\n",
    "                    if path[-1].left:\n",
    "                        lst.append(path + [path[-1].left])\n",
    "                    if path[-1].right:\n",
    "                        lst.append(path + [path[-1].right])\n",
    "                stack = lst[:]\n",
    "            return \n",
    "\n",
    "        bfs([[root]])\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    from copy import deepcopy\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        ans  = 0\n",
    "        def dp(root, nums):\n",
    "            nonlocal ans\n",
    "            if not root: return \n",
    "            for i in range(len(nums)):\n",
    "                nums[i] -= root.val\n",
    "                if nums[i] == 0: ans += 1\n",
    "            dp(root.left, nums+[targetSum])\n",
    "            dp(root.right, nums+[targetSum])\n",
    "\n",
    "        dp(root, [targetSum])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        # Helper function to perform DFS on the binary tree\n",
    "        def dfs(node, path):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            path = [p + node.val for p in path] + [node.val]\n",
    "            count = path.count(targetSum)\n",
    "            return count + dfs(node.left, path) + dfs(node.right, path)\n",
    "\n",
    "        return dfs(root, [])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        def dfs(node, path):\n",
    "            if not node:\n",
    "                return 0\n",
    "            path = [p + node.val for p in path] + [node.val]\n",
    "            count = path.count(targetSum)\n",
    "            return count + dfs(node.left, path) + dfs(node.right, path)\n",
    "        return dfs(root, [])\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "\n",
    "        # # Helper function to perform DFS on the binary tree\n",
    "        # def dfs(node, path):\n",
    "        #     if not node:\n",
    "        #         return 0\n",
    "\n",
    "        #     path = [p + node.val for p in path] + [node.val]\n",
    "        #     count = path.count(targetSum)\n",
    "        #     return count + dfs(node.left, path) + dfs(node.right, path)\n",
    "\n",
    "        # return dfs(root, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        self.count = 0\n",
    "\n",
    "        if root is None:\n",
    "            return self.count\n",
    "\n",
    "        def dfs(node: TreeNode, sum_lst: List[int]) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            sum_lst = [node.val + num for num in sum_lst]\n",
    "            sum_lst.append(node.val)\n",
    "\n",
    "            self.count += sum_lst.count(targetSum)\n",
    "\n",
    "            dfs(node.left, sum_lst)\n",
    "            dfs(node.right, sum_lst)\n",
    "\n",
    "        dfs(root, [])\n",
    "\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        self.res = 0\n",
    "        self.digui(root, targetSum, [])\n",
    "        return self.res\n",
    "\n",
    "    def digui(self, root, targetSum, numlist):\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        for i in range(len(numlist)):\n",
    "            numlist[i] += root.val\n",
    "            if numlist[i] == targetSum:\n",
    "                self.res+=1\n",
    "        numlist.append(root.val)\n",
    "        if root.val == targetSum:\n",
    "            self.res += 1\n",
    "        if root.left:\n",
    "            self.digui(root.left, targetSum, numlist[:])\n",
    "        if root.right:\n",
    "            self.digui(root.right, targetSum, numlist[:])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def dfs(node,sumlist):\n",
    "            res = 0\n",
    "            if not node:\n",
    "                return 0\n",
    "            sumlist = [num + node.val for num in sumlist]\n",
    "            sumlist.append(node.val)\n",
    "\n",
    "            count = 0\n",
    "            for num in sumlist:\n",
    "                if num == targetSum:\n",
    "                    count += 1\n",
    "            return count + dfs(node.left,sumlist) + dfs(node.right,sumlist)\n",
    "        return dfs(root,[])\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
